package arithmetic.LeetCode;


import java.util.Random;

import utils.ListNodeUtils.ListNode;

/**
 * 蓄水池算法:
 * 当内存无法加载全部数据时，如何从包含未知大小的数据流中随机选取k个数据，并且要保证每个数据被抽取到的概率相等。
 *
 *
 * https://leetcode-cn.com/problems/linked-list-random-node/solution/xu-shui-chi-chou-yang-suan-fa-by-jackwener/
 * @author jiangfeng on 2022/1/16
 */
public class RandomLink {


    /**
     * Definition for singly-linked list.
     * public class ListNode {
     * int val;
     * ListNode next;
     * ListNode() {}
     * ListNode(int val) { this.val = val; }
     * ListNode(int val, ListNode next) { this.val = val; this.next = next; }
     * }
     */
    class Solution {

        ListNode ln;
        ListNode fisrt;

        public Solution(ListNode head) {
            ln = head;
            fisrt = head;
        }

        //int index =0;

        // 我的示例 把收尾相连, 有多少个概率都随机
        public int getRandom() {
            // 1. 遍历列表获取列表长度
            // 2.
            //ln =
            //index++;
            ln = ln.next;
            if (ln == null) {
                ln = fisrt;
            }
            return ln.val;

        }
    }

    /**
     * Your Solution object will be instantiated and called as such:
     * Solution obj = new Solution(head);
     * int param_1 = obj.getRandom();
     */
    /**
     * 标准答案: 蓄水池抽样算法
     * 大数据中,用于未知样本个数, 要对样本抽样
     *
     * 蓄水池抽样算法
     * 最近经常能看到面经中出现在大数据流中的随机抽样问题
     *
     * 即：当内存无法加载全部数据时，如何从包含未知大小的数据流中随机选取k个数据，并且要保证每个数据被抽取到的概率相等。
     *
     * 当 k = 1 时，即此题的情况
     * 也就是说，我们每次只能读一个数据。
     *
     * 假设数据流含有N个数，我们知道如果要保证所有的数被抽到的概率相等，那么每个数抽到的概率应该为 1/N
     *
     * 那如何保证呢？
     *
     * 先说方案：
     *
     * 每次只保留一个数，当遇到第 i 个数时，以 1/i的概率保留它，(i-1)/i的概率保留原来的数。
     *
     * 举例说明： 1 - 10
     *
     * 遇到1，概率为1，保留第一个数。
     * 遇到2，概率为1/2，这个时候，1和2各1/2的概率被保留
     * 遇到3，3被保留的概率为1/3，(之前剩下的数假设1被保留)，2/3的概率 1 被保留，(此时1被保留的总概率为 2/3 * 1/2 = 1/3)
     * 遇到4，4被保留的概率为1/4，(之前剩下的数假设1被保留)，3/4的概率 1 被保留，(此时1被保留的总概率为 3/4 * 2/3 * 1/2 = 1/4)
     *
     * 作者：jackwener
     * 链接：https://leetcode-cn.com/problems/linked-list-random-node/solution/xu-shui-chi-chou-yang-suan-fa-by-jackwener/
     * 来源：力扣（LeetCode）
     * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
     */

    class  Solution2 {

        ListNode ln;
        Random random;


        public Solution2(ListNode head) {
            ln = head;
            random = new Random();
        }

        //  蓄水池算法
        public int getRandom() {
            int count = 0;
            int result = 0;
            while (ln != null) {
                count++;
                int r = random.nextInt(count) + 1;
                if (r == count) {
                    result = ln.val;
                }
                ln = ln.next;
            }
            return result;
        }

    }

    public static void main(String[] args) {
        for (int i = 0; i < 20; i++) {
            System.out.println(new Random().nextInt(3));

        }

    }
}
